package com.ww.springboot.boot.algorithm.tree;

/**
 * 简单二叉树输出
 *
 * @author wanwei
 * @since 2021-03-27 15:47
 */
public class TwoTreeDemo {

    //每个数字占位
    private static int k = 0;
    //总行数
    private static int n = 0;

    private static String spilt = "-";


    public static void main(String[] args) {
        method(1000);
    }

    private static void method(int total) {
        setConfig(total);
        int index = 0;
        String s = "";
        for (int i = 0; i < total; i++) {
            if (i == Math.pow(2, index) - 1) {
                n--;
                index++;
                System.out.println(s);
                s = getSpaceXX(getBefore(n));
                s += addI(i);
            } else {
                s += getSpaceXX(getSpaceMiddle(n)) + addI(i);
            }
        }
        System.out.println(s);
    }

    private static void setConfig(int total) {
        while (Math.pow(2, n) - 1 < total) {
            n++;
        }
        k = String.valueOf(total - 1).length();
    }

    private static String addI(int i) {
        String s = i + "";
        while (s.length() < k) {
            s = spilt + s;
        }
        return s;
    }

    private static String getSpaceXX(int n) {
        String s = "";
        for (int i = 0; i < k * n; i++) {
            s += spilt;
        }
        return s;
    }

    //填补前面的空格
    private static int getBefore(int n) {
        if (n == 0) {
            return 1;
        }
        double d = (1 + getBefore(n - 1) + (getSpaceMiddle(n-1) - 1) / 2);
        return (int) d;
    }


    /**
     * 填补中间的空格
     *
     * @param n
     * @return
     */
    private static int getSpaceMiddle(int n) {
        if (n == 0) {
            return 1;
        }
        //上一层空格+（上一层空格-1）/2*2  getSpaceMiddle(n - 1) + 2 + getSpaceMiddle(n - 1) - 1
        double d = (getSpaceMiddle(n - 1) * 2 + 1);
        return (int) d;
    }

}
